package com.atguigu.recursion;

/**
 * @author shkstart
 * @create 2021-08-15 19:57
 */
public class Queue8 {
    //表示有多少皇后
    int max=8;
    //数组存储皇后位置
    int [] array=new int[max];
    //解法次数
    static int count=0;
    //计算机计算的个数
    static int judgeCount=0;
    public static void main(String[] args) {
        //测试
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.println("一共有"+count+"解法");
        System.out.println("一共有"+judgeCount+"计算次数");

    }
    //放置皇后的位置
    private void check(int n){
        //n从零开始，一旦等于8，代表已经即将输入第九个皇后，可以结束
        if (n==max){
            print();
            return;

        }
        for (int i=0;i<max;i++){
            //每一个皇后都是从该行的第一列开始摆放
            array[n]=i;
            if (judge(n)){
                //如果不冲突，那接着下一个皇后的位置
                check(n+1);
            }
            //如果冲突，那该皇后的位置直接下一列

        }
    }
    //输入第n个皇后的位置，与之前进行比较
    // 说明
    //1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
    //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
    // n = 1  放置第 2列 1 n = 1 array[1] = 1
    // Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
    //3. 判断是否在同一行, 没有必要，n 每次都在递增
    private boolean judge(int n){
        judgeCount++;
        for (int i=0;i<n;i++){
            if (array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;

    }
    //输出一种方法，每个皇后摆放的位置
    private void print(){
        count++;
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}
